A lookup operation on the table with one or more columns with fields consisting of exact and wildcard values is important for many network technologies. The technologies include, but are not limited to, flow lookup in an OpenFlow switch, forwarding table lookups, policy tables, etc. The flow lookup in an OpenFlow switch will be described in this document as an exemplary embodiment. It should be noted that the described method is applicable to other technologies using both exact and/or wildcard table lookup techniques.
OpenFlow is an open standard for decoupling the control path and data path in a switch. OpenFlow aims to provide a highly configurable and flexible switch. OpenFlow works with two separate components including a controller and an OpenFlow switch as shown in FIG. 1. The controller can be located in the same device or on another device on the network. The controller controls the OpenFlow switch via a secure channel using the OpenFlow protocol. The basic concept in an OpenFlow switch lies in the notion of a flow. The flows are stored in a table called a flow table. Each flow is associated with a flow action, executed by the switch if the packet is matched against the flow. Example actions include, but are not limited to dropping a packet or forwarding a packet to a predefined port associated with the action.
The flow table consists of the flow entries with each entry made up of the 12 fields shown in Table 1 and not every field is applicable for every packet. The applicability of each field depends on the packet type as noted in the last column of the table. Each field inside the flow can be specified with exact or any value. If the flow contains at least one any value, the row is a wildcard matching flow, otherwise, the flow is an exact matching flow.
TABLE 1Flow fields in OpenFlow flow tableNo.FieldWhen applicable1Ingress portEvery packet2Ethernet source addressEvery packet on enabled-ports3Ethernet destination addressEvery packet on enabled-ports4Ethernet typeEvery packet on enabled-ports5VLAN idEvery packet with Ethernet typeequal to 0x81006VLAN priorityEvery packet with Ethernet typeequal to 0x81007IP source addressEvery packet with Ethernet typeequal to 0x0800 (IP) and0x0806 (ARP)8IP destination addressEvery packet with Ethernet typeequal to 0x0800 (IP) and0x0806 (ARP)9IP protocolEvery IP, IP over Ethernet, andARP packet10IP ToS bitsEvery packet with Ethernet typeequal to 0x0800 (IP)11Transport source port/ICMPEvery TCP, UDP, and ICMPtypepacket12Transport destination port/ICMPEvery TCP, UDP, and ICMPcodepacket
A packet arriving at the OpenFlow switch will be looked up in the flow table. If the packet matches a flow, either exact or wildcard matching flow, the specified action associated with the flow will be executed on the packet. Each wildcard matching flow has a priority assigned and if a packet matches multiple wildcard flows, the highest priority wildcard flow will be selected. An exact matching flow is always given higher priority than a wildcard matching flow. If the packet could not be matched with any flows then it will be sent to the controller for further instruction. The flow lookup is a computation-intensive task for an OpenFlow switch because the lookup must be performed on every packet.
Single Instruction Multiple Data (SIMD) is a type of parallel computing where multiple processing units process several data items concurrently. A SIMD style of processing is utilized in vector processing when the same instruction is executed on independent data items. This style of processing architecture is highly efficient for data parallel style of computing. An example of a vector processor using SIMD style of parallel computing is a graphical processing unit (GPU). The processor operates on multiple data concurrently with the condition that the instruction has to be the same for every processing unit. As a result, to fully exploit this architecture, the problem or algorithm has to be designed for data parallel processing. Because the flow lookup operation for a packet is computation intensive, as explained in the previous section, a SIMD processor is a cost effective solution for improving the lookup performance. By improving the lookup algorithm to utilize a data parallel style, several entries could be concurrently processed with a SIMD processor.
The existing solutions consist of both software and hardware based implementations. The software implementation is used in the Openflow switch reference implementation. An example of the hardware implementation is the NetFPGA OpenFlow switch reference implementation.
The software implementation lookups the flows in the flow table with the hash-then-linear lookup shown in FIG. 2. The lookup consists of two consecutive phases including hashing lookup and linear lookup phase. In the hashing lookup phase, the headers of a packet arriving to the switch will be extracted and then the hashing lookup will be performed on all of the 12 fields. If the hashing lookup found the exact matching flow, the search ends immediately. Otherwise, the search will continue to the linear lookup for wildcard matching flow. In the linear lookup phase, the search will start on the highest priority flow and go on until the end of the wildcard matching flow table as shown in FIG. 3.
The hardware implementation looks up the flow with several stages as shown in FIG. 4. The header parser component will extract fields from the packet and pack them together. Then, the packed fields will be sent to the Wildcard Lookup and the Exact Match Lookup modules. Both the Wildcard Lookup and Exact Match Lookup modules will operate simultaneously. The Exact Match Lookup module uses a hashing lookup into an off-chip static random access memory (SRAM) while the Wildcard Lookup performs its operation with on-chip ternary content addressable memory (TCAM). The result of both lookups will go into the arbiter to select the highest priority result. The arbiter will control the Packet Editor, modifying the packet according to the matched flow.
Existing solutions suffer from various drawbacks. The software based hash-then-linear lookup has a problem with the linear lookup operation for the wildcard matching flow. The processing complexity (Pc) of the linear lookup is function of the number of wildcard matching flows (n), i.e. Pc(n). In other words, the required computation steps will grow based on the number of wildcard matching flows in the flow table and therefore is not a scalable solution because of the reduction in lookup speed.
The hardware solution offers the line rate packet lookup and forwarding for both exact and wildcard matching flows. However, the hardware solution demands special and expensive hardware including SRAM for exact matching lookup and TCAM for wildcard matching lookup. Accordingly, the hardware solution will have a limited size of the flow table. The limitations for current implementations are 32000 and 32 entries for the exact matching flows and wildcard matching flows respectively. Additionally, there are limitations in space and power utilization and the need for custom chips.
Accordingly, market pressure is building for a method and system capable of providing a deterministic table lookup without requiring expensive and/or custom hardware. It is desirable that the method and system be scalable in a multi-processor and/or a multi-core computing environment.